import java.util.*;

/**
 * 547. 省份数量
 * https://leetcode-cn.com/problems/number-of-provinces/
 */
public class Solutions_547 {
    public static void main(String[] args) {
//        int[][] grid = {{1, 1, 0},
//                        {1, 1, 0},
//                        {0, 0, 1}};  // output: 2

        int[][] grid = {{1, 1, 0},
                        {1, 1, 1},
                        {0, 1, 1}};  // output: 1

        int result = findCircleNum(grid);
        System.out.println(result);
    }

    public static void union(int[] parents, int x, int y) {
        int xboss = find(parents, x);
        int yboss = find(parents, y);
        if (xboss != yboss) {
            parents[xboss] = yboss;
        }
    }

    public static int find(int[] parents, int x) {
        if (parents[x] != -1) {
            // 递归找到，老大的老大，即最终的老大，即 parents[x] == -1 的学生
            return find(parents, parents[x]);
        }
        // x 没有更大的老大了
        return x;
    }

    /**
     * 解法三：并查集（9ms）
     * int[][] grid = {{1, 1, 0},
     *                 {1, 1, 1},
     *                 {0, 1, 1}};  // output: 1
     * 以 grid 为例，通过并查集，查询“老大”的解法，得到学生 0 的“老大”是学生 1
     * 学生 1 的“老大”是学生 2，学生 2 最终没有最大的“老大”了，说明是一个朋友圈中的“老大”
     */
    public static int findCircleNum(int[][] M) {
        int len = M.length;
        int res = 0;
        // parents[0] = 1，表示学生 0 与学生 1 处于一个朋友圈中，并且以 1 为“老大”
        int[] parents = new int[len];
        // 默认情况下，len 个学生都互不为朋友
        Arrays.fill(parents, -1);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (i != j && M[i][j] == 1) {
                    // 两个学生处于一个朋友圈时，parents 进行合并
                    union(parents, i, j);
                }
            }
        }
        for (int i = 0; i < len; i++) {
            // parents[i] = -1 时，说明该学生是朋友圈的“老大”，parents 中“老大”的个数就是
            // 最终朋友圈的个数，就是数“老大”的数量
            // 因为不是“老大”的学生，已经将学生 i 的 parents[i] 置为了其“老大”
            res += parents[i] == -1 ? 1 : 0;
        }
        return res;
    }

    /**
     * 解法二：广度优先搜索-bfs（10ms）
     */
    public static int findCircleNum3(int[][] M) {
        int res = 0;
        Queue<Integer> queue = new LinkedList<>();
        // visited[1] = true，学生 1 在一个朋友圈中，visited[2] = false，学生 2 不在朋友圈中，需要加入
        boolean[] visited = new boolean[M.length];
        for (int i = 0; i < M.length; i++) {
            if (!visited[i]) {
                queue.add(i);
                while (!queue.isEmpty()) {
                    int j = queue.poll();
                    visited[j] = true;
                    // 查找学生 j 的全部朋友
                    for (int k = 0; k < M.length; k++) {
                        if (M[j][k] == 1 && !visited[k]) {
                            // j 与 k 互为朋友，且 k 未加入到朋友圈，那么 k 入列，后续查找与 k 互为朋友的学生
                            queue.add(k);
                        }
                    }
                }
                // 一个朋友圈中的朋友，全部添加/标记
                res ++;
            }
        }
        return res;
    }

    /**
     * 解法一：深度优先搜索-dfs（1ms）
     */
    private static int n = 0;
    public static int findCircleNum2(int[][] M) {
        n = M.length;
        // visited[1] = true，学生 1 在一个朋友圈中，visited[2] = false，学生 2 不在朋友圈中，需要加入
        boolean[] visited = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 第 i 个学生未访问过，说明 i 是在一个独立的朋友圈，朋友圈数量加 1
                res++;
                visited[i] = true;
                // 深度优先搜索，将与 i 在同一个朋友圈的，在 visited 中都置为 true
                dfs(M, visited, i);
            }
        }
        return res;
    }

    public static void dfs(int[][] m, boolean[] visited, int i) {
        // 遍历第 i 行中的列，判断学生 i 与哪些学生在同一个朋友圈
        for (int j = 0; j < n; j++) {
            if (m[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                // 因为学生 i 与学生 j 互为朋友，那么继续递归，查找与 j 互为朋友的学生
                dfs(m, visited, j);
            }
        }
    }
}